import java.util.ArrayList; 

class Fila{
    private ArrayList<Documento> heap = new ArrayList<>(); //cria uma árvore (heap) com o ArrayList

    // adiciona um novo documento na árvore, seguindo os conceitos de fila (FIFO) e heap: ou seja, põe os elementos por ordem de prioridade
    public void adicionarDocumento(Documento novo){
	heap.add(novo); // adiciona o novo documento na árvore 
	int indice = heap.size() - 1; // ID do índice: recebe o tamanho da árvore menos um
	while(indice > 0){ // enquanto o índice for maior que 0 
	    int pai = (indice - 1) / 2; // ID do pai. OBS: se resultar em número decimal, a parte decimal é ignorada. Por exemplo: 0.5 é 0. 
	    if(heap.get(pai).prioridade() < heap.get(indice).prioridade()){ // se a prioridade do pai for menor que a do índice
		// troca
		Documento tmp = heap.get(pai); // objeto temporário para possibilitar colocar o objeto pai na posição do índice
		heap.set(pai, heap.get(indice)); // coloca o objeto do índice na posição do pai 
		heap.set(indice, tmp); // coloca o objeto pai na posição do índice
		//
		indice = pai; // o ID do índice recebe o ID do pai 
	    } else {
		break; // encerra o while se a prioridade do pai for igual ou maior que a do índice
	    }
	}
    }

    // imprime e remove o documento que é o nó máximo (topo) da árvore e também pode fazer os demais documentos 'subirem' na árvore
    public Documento imprimir(){
	Documento noMaximo = heap.get(0); // o objeto noMaximo é o topo 
	heap.set(0, heap.get(heap.size() - 1)); // coloca no topo o objeto abaixo 
	heap.remove(heap.size() - 1); // remove o objeto abaixo (antigo topo) 

	int indice = 0;
	while(indice < heap.size()){ // enquanto o índice for menor que a árvore
	    int filhoEsquerdo = indice * 2 + 1; // ID do filhoEsquerdo 
	    int filhoDireito = indice * 2 + 2; // ID do filhoDireito
	    int filhoMaior = filhoEsquerdo; // ID do filho de maior prioridade é o do filhoEsquerdo

	    // se o ID do filhoDireito for menor que o tamanho da árvore e, ao mesmo tempo, a prioridade do filhoDireito for maior que a do filhoEsquerdo
	    if(filhoDireito < heap.size() && heap.get(filhoDireito).prioridade > heap.get(filhoEsquerdo).prioridade){
		filhoMaior = filhoDireito; //filhoMaior recebe o filhoDireito, isto é, o filhoDireito sobe na árvore
	    }

	    // se o ID do filhoMaior for menor que o tamanho da árvore e, ao mesmo tempo, a prioridade do filho maior for maior que a prioridade do 'índice' 
	    if(filhoMaior < heap.size() && heap.get(filhoMaior).prioridade > heap.get(indice).prioridade){
		//troca
		Documento tmp = heap.get(filhoMaior); // objeto temporário para possibilitar colocar o filhoMaior na posição do índice
		heap.set(filhoMaior, heap.get(indice)); // coloca o objeto do ínice na posição do filhoMaior
		heap.set(indice, tmp); // coloca o filhoMaior na posição do índice
		//
		indice = filhoMaior; // o ID do índice recebe o ID do filhoMaior 
	    } else {
		break; // encerra o while se o filhoMaior for maior ou igual ao tamanho da árvore ou a prioridade do filhoMaior for menor ou igual que a do índice 
	    }
	}
	return noMaximo; // retorna o noMáximo, ou seja, o topo 
    }
    
    // returna true se a árvore estiver vazia ou false se a árvore estiver cheia 
    public boolean estaVazia(){
	return heap.isEmpty(); 
    }

}
